
def isPrime(n):
	'''check if int n is a prime'''
	if n == 1 or n == 0:
	    return False
	for x in range(2, int(n**0.5)+1):
		if n % x == 0:
			return False
	return True

def genTriNumbers(n):
	TRI_NUMS = []
	i = 1
	sum = 0
	while i <= n:
		sum += i
		TRI_NUMS.append(int(sum))
		i += 1
	return TRI_NUMS

def getPrimes(n):
    if n==2: return [2]
    elif n<2: return []
    s=range(3,n+1,2)
    mroot = n ** 0.5
    half=(n+1)/2-1
    i=0
    m=3
    while m <= mroot:
        if s[i]:
            j=(m*m-3)/2
            s[j]=0
            while j<half:
                s[j]=0
                j+=m
        i=i+1
        m=2*i+3
    return [2]+[x for x in s if x]


def getFactors(n,proper = False):
	FACTORS = []
	i = 1
	while i <= n:
		if n % i == 0:
			if i in FACTORS:
				return FACTORS
			if proper and not i == n:
				FACTORS.append(i)
			elif not proper:
				FACTORS.append(i)
		i += 1
	return FACTORS

def getNumDivisors(n):
    #PRIMES = getPrimes(n/2)
    #print PRIMES
	PRIMES = getPrimes(14000000)
	factor_map = {}
	tmp = n
	for i in PRIMES:
		while tmp % i == 0:
			if i in factor_map.keys():
				factor_map[i] += 1
			else:
				factor_map[i] = 1
			tmp = tmp / i
			if tmp == 1:
				break
		if tmp == 1:
			break
	prod = 1
	for key in factor_map.keys():
		prod *= factor_map[key]+1
	return prod

DAYS = {1:"MONDAY",
        2:"TUESDAY",
        3:"WEDNESDAY",
        4:"THURSDAY",
        5:"FRIDAY",
        6:"SATURDAY",
        7:"SUNDAY"}

MONTHS = {  1:"JANUARY",
			2:"FEBRUARY",
			3:"MARCH",
            4:"APRIL",
            5:"MAY",
            6:"JUNE",
            7:"JULY",
            8:"AUGUST",
            9:"SEPTEMBER",
            10:"OCTOBER",
            11:"NOVEMBER",
            12:"DECEMBER"}

MONTH_DAYS = { 	"JANUARY":31,
            	"FEBRUARY":28,
            	"MARCH":31,
            	"APRIL":30,
            	"MAY":31,
            	"JUNE":30,
            	"JULY":31,
            	"AUGUST":31,
            	"SEPTEMBER":30,
            	"OCTOBER":31,
            	"NOVEMBER":30,
            	"DECEMBER":31}

LEAP_MONTH_DAYS = { "JANUARY":31,
                	"FEBRUARY":29,
                	"MARCH":31,
                	"APRIL":30,
                	"MAY":31,
                	"JUNE":30,
                	"JULY":31,
                	"AUGUST":31,
                	"SEPTEMBER":30,
                	"OCTOBER":31,
                	"NOVEMBER":30,
                	"DECEMBER":31}

def fact(n):
	if n == 1 or n == 0:
		return 1
	else:
		return n*fact(n-1)

LTRMAP = {  "A":1,
			"B":2,
			"C":3,
			"D":4,
			"E":5,
			"F":6,
			"G":7,
			"H":8,
			"I":9,
			"J":10,
			"K":11,
			"L":12,
			"M":13,
			"N":14,
			"O":15,
			"P":16,
			"Q":17,
			"R":18,
			"S":19,
			"T":20,
			"U":21,
			"V":22,
			"W":23,
			"X":24,
			"Y":25,
			"Z":26}

def isPalindrome(pal):
    flip = ""
    for i in range(len(pal)-1,-1,-1):
        flip += pal[i]
    return flip == pal

def isNPandigital(num,n):
    numStr = str(num)
    for i in range(1,n+1):
        if not numStr.__contains__(str(i)):
            return False
    return True

def gcd(a,b):
    if b % a == 0:
       return a
    multB = b
    multA = a
    while 1:
        if multA > multB:
            multB += b
        elif multA < multB:
            multA += a
        else:
            return (a*b)/multA